As is known, computer systems are tested to verify that the systems are compliant with their intended architecture. Compliance may be verified, for example, by stimulating the computer system with various sets of valid inputs, typically consisting of machine instructions and interrupts (internal and/or external). Modern computer systems are typically complex, and may be capable of handling many different instructions and interrupts. It is often difficult to determine a priori precisely which instructions within a particular system's instruction set are most likely to exhibit noncompliance: for this reason, randomly generated, biased instruction streams are often used as an effective and efficient way to reveal system compliance errors. In practice, pseudo-random instruction streams are often used, typically generated by using an initial or “seed” value and an instruction selection algorithm (or test generation program) which uses the seed as an input. As used herein, “random” and “pseudo-random” are used interchangeably. Furthermore, in order to utilize the knowledge and experience of system architects and test engineers regarding the machine instructions which may be of greatest concern, a set of instruction biases may be used, providing guidance to the test generation algorithm as to the relative frequency with which each instruction should be used in the resulting instruction stream. An instruction stream generated in accordance with a set of biases is referred to as a biased instruction stream. To enable the greatest possible test coverage of the instruction set, and therefore the greatest possible probability of error detection, all instruction types should be available for inclusion in a test instruction stream. In particular, both forward branching and backward branching instructions should be available for inclusion within a test instruction stream.
A randomly generated, biased instruction stream should constitute a terminating computer program, in order to maximize test efficiency. Each set of machine instructions comprising a randomly generated, biased instruction stream includes, in general, operands, addresses, and the sequence in which the instructions are executed: each such instruction stream is, therefore, a computer program. While the instruction syntax should be correct, the semantics of the resulting computer program is not generally relevant from a test viewpoint. However, unless appropriate control mechanisms are used, a randomly generated instruction stream in which all instruction types may be used, could form a non-terminating instruction stream (i.e., a non-terminating program). A non-terminating test instruction stream may drastically reduce the efficiency of testing, by causing the computer system to repeatedly execute only a portion of the intended test instruction stream.
A computer program comprising a randomly selected stream of instructions is unlikely to simultaneously achieve both high test coverage, and termination. As previously noted, inclusion of forward branching and backward branching instructions in a test instruction stream is desirable, from a test coverage viewpoint. Inclusion of these instruction types, however, may result in loops or recursions within the computer program or instruction stream. Programs including loops or recursions are not, in general, guaranteed to terminate. Determining whether or not a program terminates, when the program contains loops or recursions, is related to the well-known “halting problem,” for which there is, in general, no particular solution. There are, for example, real-life programs which are designed to run forever. Typically, a terminating loop includes three essential loop components: an initialization, one or more controlling conditions, and one or more iteration incrementing statements. A loop in a program or instruction stream generated by a random generation algorithm, however, may lack one or more of these essential loop components, such as a proper iteration incrementing statement. As a result, a randomly generated instruction stream containing one or more branching instructions may, in general, never terminate. Several methods are known in the art to detect non-terminating loops in computer programs or instruction streams in general. For example, methods such as loop invariant analysis, loop unfolding, and data flow graphs may be used to determine whether or not a specific computer program is likely to terminate within a finite number of iterations.
Loop invariant analysis may be used to determine whether a particular computer program is likely to terminate. A loop invariant is an expression which shows the progress that successive iterations of the loop make toward satisfying the exit condition(s) of the loop. Thus, the invariant of the loop is directly related to the loop exit condition expression. For the loop to terminate after a finite number of iterations, at least one variable of its exit condition expression must change its value within the loop. In addition, these changes must lead toward the loop exit condition. In contrast, a loop invariant expression in which none of the loop variables changes value indicates a loop which does not terminate, or which cannot be executed. While loop invariant analysis may detect non-terminating loops, identifying the loop invariant is often not a straightforward process, and frequently requires human interaction and analysis.
Loop unfolding may also be used to determine whether a particular computer program is likely to terminate. Loop unfolding is discussed in, for example, R. Vemuri and R. Kalyanaraman, “Generation of Design Verification Tests from Behavioral VHDL Programs using Path Enumeration and Constraint Programming,” IEEE Transactions on VLSI Systems, vol. 3, No. 2, June 1995, pp. 201-214. According to the loop unfolding method, a loop is replaced with a sequence of if-then-else constructs. Statements in the loop body are copied within the new constructs. Each time a new if-then-else construct is created, the exit condition is checked. Depending upon the exit condition status, the loop is either found to be terminating or further loop unfolding is performed. The loop unfolding process is continued until either the loop is found to be terminating, or an iteration threshold is reached in which case the loop is considered potentially non-terminating. While loop unfolding may also detect non-terminating loops, the process is also time consuming and likely to require some analysis such as finding loop upper bounds.
Directed acyclic graphs (DAGs) may also be used to determine whether a particular computer program is likely to terminate. Directed acyclic graphs are discussed in, for example, C. Healy, et. al., “Bounding Loop Iterations for Timing Analysis,” Proceedings of Technology and Application Symposium, 1998, pp. 12-21. The DAG method predicts the execution time of natural loops (i.e., loops with single entries) whose iterations depend upon counter variables. A DAG representing the loop is constructed. The nodes of the DAG consist of condition and continue branches, as well as break nodes. The continue and break nodes signify the back edges and transitions out of the loop, respectively. Conditional branches which affect the loop iterations, termed iteration branches, are identified. A table is constructed containing relevant information for each iteration branch, such as variable values before and after the branch is traversed. An iteration branch is classified as known if the pertinent information in the table is completed. The number of times a branch can be taken is derived from the table. For the case when the iteration is unknown, the maximum range is assigned to each outgoing edge of the node. The maximum and minimum iteration of the root node of the DAG become the maximum and minimum iterations of the loop, respectively. Further work is needed to handle cases where loops are nested and when the counters are incremented in a variable manner.
The above methods are intended for use in analyzing computer programs in general, and share a number of common attributes that may be unnecessary and/or undesirable within the more specific realm of test program generation. In particular, as previously noted, within the field of test program generation, test program semantics are not a consideration, in contrast with computer program generation in general. The methods described, therefore, focus on determining whether a specific instruction set is likely to terminate, rather than on modifying or influencing the instruction stream to insure termination. Such modification could alter the program semantics, and may therefore be undesirable in general. Also, while some degree of human analysis and interaction may be desirable or necessary within the field of programming in general, test program generation is preferably performed in an automated environment. In the field of test generation, minimal post-generation analysis and modification is highly desirable.
U.S. Pat. No. 5,956,478 to Huggins, entitled “Method for Generating Random Test Cases Without Causing Infinite Loops,” discloses a method of generating random test streams, including backward branching instructions. Non-terminating (or infinite) loops are prevented in two ways. First, creation of loops at the macroscopic level is prevented entirely, by segmenting the test instruction stream into blocks or instructions, and allowing no more than one branch path into each block of instructions. Second, each instruction group may contain one or more controlled (i.e., terminating) loops, such as those formed by a branch on count instruction.
For the foregoing reasons, therefore, there is a need in the art for a method of generating a random test instruction stream, including both forward and backward branching instructions, where the instruction stream is guaranteed to terminate.